package HOT;

import java.util.HashMap;
import java.util.Map;

/**
 * Author  zxy
 * Date  2023/6/15 下午 5:11
 */
public class SubArraySum {
    public int subarraySum(int[] nums, int k) {

        int cnt = 0;
        int len = nums.length;

        // 暴力
        // for (int i = 0; i < len; i++) {
        //     int sum = 0;
        //     for (int j = i; j >= 0; j--) {
        //         sum += nums[j];
        //         if (sum == k) {
        //             cnt++;
        //         }
        //     }
        // }

        // 哈希表+前缀和
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int pre = 0;

        for (int i = 0; i < len; i++) {
            pre += nums[i];

            if (map.containsKey(pre - k)) {
                cnt += map.get(pre - k);
            }

            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }

        return cnt;
    }
}
